/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cs;

/**
 *
 * @author QuangHieu
 */
class ANode{
    int data;
    ANode left,right;
    ANode(int x){
        data=x;
        left=right=null;
    }
    ANode(int x, ANode ll, ANode rr){
        data=x;
        left=ll;
        right=rr;
    }
}

class CayAVL {

    ANode root;

    CayAVL(){
        root=null;
    }
    
    ANode qL(ANode x){
        ANode y=x.left;
        ANode z=y.right;
        x.left=z;
        y.right=x;
        return y;
    }

    ANode qR(ANode x){
        ANode y=x.left;
        ANode z=y.left;
        x.right=z;
        y.left=x;
        return y;
    }

    ANode qRL(ANode x){
        ANode y=x.left;
        //ANode z=y.left;
        ANode t=y.right;
        ANode m1=t.left;
        ANode m2=t.right;
        y.left=m1;
        x.left=m2;
        t.left=y;
        t.right=x;
        return t;
    }

    ANode qLR(ANode x){
        ANode y=x.right;
        ANode t=y.left;
        ANode m2=t.right;
        ANode m1=t.left;
        x.right=m1;
        y.left=m2;
        t.left=x;
        t.right=y;
        return t;
    }

    private int chieuCao(ANode t){
        if(t==null)
            return 0;
        return 1+ Math.max(chieuCao(t.left),chieuCao(t.right));
    }

    private ANode insert(ANode t, int x){
        if(t==null)
            return new ANode(x);
        if(x<t.data)
            t.left=insert(t.left,x);
        else if(x>t.data)
            t.right=insert(t.right,x);
        else {
            System.out.print("Da co trong cay!");
            return t;
        }
        int h1=chieuCao(t.left);
        int h2=chieuCao(t.right);
        if(h1>h2+1){
            int h11=chieuCao(t.left.left);
            int h12=chieuCao(t.left.right);
            if(h11>h12)
                return qL(t);
            else
                return qRL(t);
        }
        else if(h2>h1+1){
            int h22=chieuCao(t.right.right);
            int h21=chieuCao(t.right.left);
            if(h22>h21)
                return qR(t);
            else
                return qLR(t);
        }
        return t;
    }

    void insert(int x){
        root= insert(root, x);
    }
        // duyet trung tu
    private void duyetTrungTu(ANode t){
        if(t!=null){
            duyetTrungTu(t.left);
            System.out.print(" "+t.data);
            duyetTrungTu(t.right);
        }
    }

    void duyetTrungTu(){
        duyetTrungTu(root);
    }

    private void taoCay(){
        root=null;
        int a[]={40,21,15,26,28,34,14,17,9,33,55,56,15};
        for(int i=0;i<a.length;i++)
            insert(a[i]);
    }

    public static void main(String []args){
        CayAVL avl=new CayAVL();
        avl.taoCay();
        avl.duyetTrungTu();
    }
}
